/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <algorithm>
using namespace std;
class Solution {
    bool isBalanced(TreeNode *root, int &h) {
        if (root==NULL) {
            h=0;
            return true;
        }
        int lh, rh;
        if (!isBalanced(root->left, lh) || !isBalanced(root->right, rh) || abs(lh-rh)>1) return false;
        h=max(lh, rh)+1;
        return true;
    }
public:
    bool isBalanced(TreeNode *root) {
        int h;
        return isBalanced(root, h);
    }
};
